package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _47_permutation {
    
    static class chao {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> perm = new ArrayList<>();
        boolean[] vis;
        public List<List<Integer>> permuteUnique(int[] nums) {
            vis = new boolean[nums.length];
            Arrays.sort(nums);
            backtrack(nums, 0);
            return ans;
        }
        public void backtrack(int[] nums, int idx) {
            if (idx == nums.length) {
                ans.add(new ArrayList<>(perm));
                return;
            }
            for (int i = 0; i < nums.length; ++i) {
                // 我想问一嘴，这个判断是怎么回事？
                /*
                * 听说是关注取消选择。
                * 上一个选了，自己可以选可以不选，无所谓不影响结果
                * 上一个不选，自己如果选了，结果相当于上一个选了？是这个意思吗
                * 感觉不太对
                *
                * 以后再说吧，先背过
                *
                * */
                if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                    continue;
                }
                perm.add(nums[i]);
                vis[i] = true;
                backtrack(nums, idx + 1);
                vis[i] = false;
                perm.remove(perm.size() - 1);
            }
        }
        
    }
    
    static class Solution {
        boolean[] vis;
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            List<Integer> perm = new ArrayList<>();
            vis = new boolean[nums.length];
            Arrays.sort(nums);
            backtrack(nums, ans, 0, perm);
            return ans;
        }
        public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
            if (idx == nums.length) {
                ans.add(new ArrayList<>(perm));
                return;
            }
            for (int i = 0; i < nums.length; ++i) {
                if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                    continue;
                }
                perm.add(nums[i]);
                vis[i] = true;
                backtrack(nums, ans, idx + 1, perm);
                vis[i] = false;
                perm.remove(perm.size() - 1);
            }
        }
    }
}
